package code;

public class Code105 {
	/*
	 * 与106同类型的题
	 * 已知二叉树的先序遍历和中序遍历，构建出二叉树
	 * 递归求解，好写。
	 * 看代码
	 *
	 */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
    	/*
    	 * 只有一个元素，直接返回自己
    	 */
    	int n=inorder.length;
    	if(n==0)	return null;
    	TreeNode p=new TreeNode(preorder[0]);
    	
    	if(n==1){
    		return p;
    	}
    	int i;
    	for(i=0;i<n;i++){
    		if(inorder[i]==preorder[0])
    			break;
    	}
    	/*
    	 * 构建左子树
    	 */
    	//有左子树
    	if(i>0){
    		int[] leftInorder=new int[i];
    		int[] leftPreorder=new int[i];
    		for(int j=0;j<i;j++){
    			leftInorder[j]=inorder[j];
    			leftPreorder[j]=preorder[j+1];
    		}
    		p.left=buildTree(leftPreorder,leftInorder);
    	}
    	/*
    	 * 构建右子树
    	 * 如果存在右子树的话
    	 */
    	if(i<n-1){
    		int[] rightInorder=new int[n-i-1];
    		int[] rightPreorder=new int[n-i-1];
    		for(int j=i+1;j<n;j++){
    			rightInorder[j-i-1]=inorder[j];
    			rightPreorder[j-i-1]=preorder[j];
    		}
    		p.right=buildTree(rightPreorder,rightInorder);
    	}
		return p;
    }
    public void dfs(TreeNode p){
    	System.out.println(p.val);
    	if(p.left!=null)
    		dfs(p.left);
    	if(p.right!=null)
    		dfs(p.right);
    }
    public static void main(String[] args){
    	Code105 code=new Code105();
//    	int[] preorder={1,2,4,5,3,6,7};
//    	int[] inorder={4,2,5,1,6,3,7};
    	int[] preorder={2,4,5};
    	int[] inorder={4,2,5};
    	TreeNode root=code.buildTree(preorder,inorder);
    	code.dfs(root);
    }
}
